package com.lw.leetcode.binary.a;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1608. 特殊数组的特征值
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/4 13:33
 */
public class SpecialArray {

    public static void main(String[] args) {
        SpecialArray test = new SpecialArray();

        // -1
        int[] arr = {0, 0};

        // 2
//        int[] arr = {3, 5};

        // 3
//        int[] arr = { 0,4,3,0,4};

        // -1
//        int[] arr = { 3,6,7,7,0};

        // 5
//        int[] arr = { 5,6,7,8,9};
        int i = test.specialArray(arr);
        System.out.println(i);
    }

    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int end = nums[nums.length - 1];
        int st = 0;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            int i = find(nums, m);
            if (i == m) {
                return i;
            } else if (i < m) {
                end = m - 1;
            } else {
                st = m + 1;
            }
        }
        return -1;
    }

    private int find(int[] arr, int t) {
        if (t <= arr[0]) {
            return arr.length;
        }
        int st = 0;
        int end = arr.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return arr.length - 1 - st;
    }
}
